class Solution(object):
    def exist(self, board, word):
        """
        :type board: List[List[str]]
        :type word: str
        :rtype: bool
        """
        if not board or not board[0]:
            return False

        rows, cols = len(board), len(board[0])

        def backtrack(i, j, k):
            if board[i][j] != word[k]:
                return False
            if k == len(word) - 1:
                return True

            tmp, board[i][j] = board[i][j], '#'
            for x, y in [(0,1), (0,-1), (1,0), (-1,0)]:
                ni, nj = i + x, j + y
                if 0 <= ni < rows and 0 <= nj < cols and board[ni][nj] != '#':
                    if backtrack(ni, nj, k + 1):
                        board[i][j] = tmp
                        return True
            board[i][j] = tmp
            return False

        for i in range(rows):
            for j in range(cols):
                if backtrack(i, j, 0):
                    return True
        return False